1. Field of the Invention
The present invention relates to a method and device for parallel storage allocation in electronic computers.
2. Description of Related Art
In electronic computers such as microcomputers which incorporate a memory device, space in the memory which has been used must be made available for reuse in an efficient manner. FIG. 1a illustrates the relationship between a processing device and a memory device having the facility for controlling memory space usage.
Referring to FIG. 1a, a memory device 100 comprises a distribution (allocation) section 100a, a memory section 100b, a delay (defer) processing section 100c and a clear control section 100d. Communications channels 101 and 102 lead from processing device 103 to the memory device 100 and from the memory device 100 to the processing device 103 respectively.
The exchange of information between the operating device 103 and the memory device 100 is all done by the transmission of single data packets, hereinafter referred to as "tokens". When the distribution section 100a of the memory device 100 receives a memory space request token 104 it sends a start address for the space (which depends on the size of space required) in the form of a token 105. The memory section 100b can also receive a write token 106 or a read request token 107. In response to the former, the memory 100b enters the parameter V into address A, and in response to the latter reads the contents V of address A, and sends the result to the processing device 103 in the form of a data token 108. Except in the case of the write token WRT, a response to the processing device is necessary, and such responses are identified by parameters Ra. Tokens are not sent directly between the delay management section 100c or the clear control device 100d and the operating device 103. The delay management section 100c and the memory section 100b respectively perform the operations of handling read request tokens relating to data which has not yet arrived in the memory section and clearing memory space which the clear control device 100d has finished using. The different types of token can be recognized from a code in each token.
FIG. 1b illustrates schematic examples of each kind of token. Referring to FIG. 1b, each token comprises four fields, namely a code field 451, a second field 452, a third field 453, and a fourth field 454.
The code field 451 is the one used to distinguish between different kinds of token. In the example of FIG. 1 it is allotted four bits, from which can be represented sixteen different kinds of token. For the sake of simplicity, the illustrated fields 452 to 454 each comprise 24 bits, but any length can be selected to suit a particular system. Shaded areas in the diagrams are fields which are not used.
FIGS. 2a to 2c illustrate in detail the functions of the above-mentioned distribution section 100a and memory section 100b. The distribution section 100a seeks and reserves memory space (hereinafter referred to as "space") which is not in use to meet the requirements of the processing device 103. Then it sends a pointer token which identifies the reserved space to the processing device 103. Referring to FIG. 2a, channels 201 and 202 carry tokens from and to the processing device 103 respectively, and correspond to the parts labelled 101, 102 in FIG. 1a. A distribution table 220 comprises the following items: a valid flag 221, a size field 222, and a start address field 223. When the valid flag 221 is 1 this means that the space to which the associated fields 222 and 223 relate is not in use, that is "free". The size field 222 and start address field 223 contain the size and start address of the free space.
The status address of each space in memory section 100b and the last address of the space comprise a free flag 224 and a size flag 225. When the free flag 224 is "1", this means its space is not in use; size flag 225 holds the same contents as the size field of the distribution table 220.
A space request token SRQ 203 which is sent from the processing device 103 to the distribution device 100a includes the two parameters Zr, the size of the space required, and Ra. The workings of this system will now be described in greater detail.
(1) Referring to FIG. 2a, when the space request token 203 (SRQ) arrives, the distribution section 100a checks the distribution table 220 and searches for an address which stores a value as large as the value for the parameter Zr of the space request token SRQ 203. If such an address is found, the parameter Ra of the space request and the start address of the related space are associated. For example, as shown in FIG. 2b, the address related to space N may be located, and if so a pointer token (PNT) 204 is generated.
At the same time, "0" is entered in the valid flag of the corresponding address in the distribution table 220. Entering "0" in the valid flag 221 for space N indicates that the space N is now in use.
When not enough space can be found to fulfill the space requests of the distribution section 100a, an overflow occurs which has a characteristic control signal, and the processing device 103 is notified that the program cannot progress any further. Since this does not have any direct bearing on the present invention, it will not be discussed in detail herein.
When a space (M, for example) in the memory device 100b was being used but is no longer in use, the memory device 100b detects this condition. If the space next to the space M is free, then the said space next to M and M are considered as a single combined space and recorded as such in the table 220. If there is no free space adjacent to space M, M alone is recorded in the table 220. FIG. 2b illustrates the processes which occur when use of the space M is finished (i.e. when the space M has become free).
(2) The memory section 100b investigates the free flag of addresses adjacent, to space M, namely address (SM-1) and address (SM+ZM). (SM+ZM=SN). Since the valid flag of the address SN is "0", nothing is done with respect to the space N which is in use. Since the valid flag of the address SM-1 is "1", it is known that the space L is free. The start address SL of the space L is calculated from the size field (SL=SM-ZL). The start address SL of the space formed from the joining together of the space L and the space N, and its size (ZL+ZM) are calculated.
(3) The distribution section 100a and the distribution table 220 are checked, and the address holding the value SL in the start address field is sought, and referring to FIG. 2c, the value ZL+ZM is entered in the size field of this address.
When free spaces have not been joined together by the action of the memory section 100b (as explained in (2) above), the address which holds the start address (SM) of the space to be registered is not present in the distribution table 200. Accordingly the start address SM and the size ZM are entered into an address in which the valid flag is "0", and the valid flag is changed to "1".
In the above system, when a memory block is no longer in use, it is not possible to inform the distribution table directly and then re-write the start address of the space and the last address at the same time. This has the disadvantage that tokens are processed too slowly. Furthermore, when the above-mentioned two processes are carried out in accordance with the procedure described above, logical contradictions arise. This problem will now be explained with reference to FIGS. 3 and 4a to 4h.
FIG. 3 shows a system wherein the distribution section 100a and the memory section 100b are separated, and communication between them is carried out entirely by means of tokens. The word "separated" hereinafter means communicating completely by means of sending tokens.
In FIG. 3, token channels 306 and 307 connect the distribution section 100a and the memory section 100b. The channels carry a space request token (RSV) 308 and a liberate space token (LIB) 309. The space request token results from the distribution section 100a seeking to turn free space into space in use, and the liberate space token (LIB) 309 results from free space becoming available which must be recorded in the distribution table. The problems of this system are explained with reference to FIGS. 4a to 4h. FIG. 4a shows the same kind of situation as FIG. 2a, and a space request token (SRQ) 303 is being sent from the processing device 103. In the memory, spaces L and N are free, and space M is in use. The process will be explained below: